#include<iostream>
#include<math.h>

using namespace std;

const int MAX_STR_LEN = 100;
const int END_OF_DATA = -1;
const int MAX_ARR_LEN = 100;

void printBoolRes(bool flag);
void printArr(int arr[], int size);

int count_ones_in_binary(int num)
{
	if(num == 0) return 0;
	if(num == 1) return 1;
	return count_ones_in_binary(num%2) + count_ones_in_binary(num/2);
	
}

bool contain_sequences_of_evens(int num)
{
	if(num < 10) return false;
	return (((num%10)%2==0)&&(((((num/10)%10))%2)==0)) || contain_sequences_of_evens(num/10);
}
int biggest_low_power(int x, int num)
{
	if(num < x) return 1;
	if(num < x*x) return x;
	return x * biggest_low_power(x, num/x);

}
int part_sum(int num)
{
	if(num<10) return 0;
	return part_sum(num/10) + num/10%10;
}
int read_array(int data[])
{
	int input;
	int count;
	count = 0;
	cin >> input;
	while(input!= -1)
	{
		data[count]=input;
		count++;
		cin >> input;
	}
	return count;
}
void bubble_sort(int data[], int size)
{
	int i, j, swap;
	for(i=0;i<size-1;i++)
		for(j=0;j< size - i -1;j++)
			if(data[j] > data[j+1])
			{
				swap=data[j];
				data[j] = data[j+1];
				data[j+1] = swap;
			}
}
void partition(int data[], int size)
{
	int val;
	int i;
	int index;
	int swap;
	val = data[0];
	index=0;
	for(i=0;i<size;i++)
	{
		if(val>data[i])
		{
			swap = data[index+1];
			data[index] = data[i];
			data[index+1] = val;
			data[i] = swap;
			index++;

		}

	}
	if(index == size - 1) data[index] = val;
}
double find_avg(int data[], int size)
{
	int sum;
	int i;
	sum = 0;
	for(i=0;i<size;i++)
		sum+=data[i];
	return (double)sum / size;
}

double find_avg_two_arr(int data1[], int data2[], int size1, int size2)
{
	return (find_avg(data1, size1)*size1 + find_avg(data2, size2)*size2)/(size1+size2);
}
double find_median(int sorted_data[],int size)
{
	return sorted_data[size/2 -1];
}
double find_median_two_arr(int sorted_data1[], int sorted_data2[], int size)
{
	if(find_median(sorted_data1, size) == find_median(sorted_data2, size)) return find_median(sorted_data1, size);
	if(find_median(sorted_data1, size) < find_median(sorted_data2, size)) 
		return find_median_two_arr(sorted_data1+1, sorted_data2, size -1);
	if(find_median(sorted_data1, size) > find_median(sorted_data2, size)) 
		return find_median_two_arr(sorted_data1, sorted_data2+1, size -1);
}

int main()
{
	int choice; // for menu
	int res; // returned value from user function
	bool boolres; // returned boolean value from user function
	int i; //index for input loops
	int num, num2;  // user input
	char strin[MAX_STR_LEN]; //user string input
	int data1[MAX_ARR_LEN], data2[MAX_ARR_LEN]; //user array of input data
	int resData[MAX_ARR_LEN]; //output array from functions
	int dataSize, dataSize1, dataSize2; //logical size of data
	double avg1, avg2, avg_all; //average results
	int median, median1, median2; //median results

	cout << "Press 1 for section 1\n";
	cout << "Press 2 for section 2\n";
	cout << "Press 3 for section 3\n";
	cout << "Press 4 for section 4\n";
	cout << "Press 5 for sections 5,6 and 7\n";
	cout << "Press 6 for sections 5,6,8 and 10\n";
	cout << "Press 7 for sections 5 and 9\n";
	cout << "Press 8 for sections 5,6 and 11\n";

	cin >> choice;

	switch (choice)
	{
	case 1:
		for (i = 1; i <= 4; i++)
		{
			cin >> num;
			res = count_ones_in_binary(num);
			cout << res << " ";
		}
		cout << endl;
		break;

	case 2:
		for (i = 1; i <= 4; i++)
		{
			cin >> num;
			boolres = contain_sequences_of_evens(num);
			printBoolRes(boolres);
		}
		cout << endl;
		break;

	case 3:
		for (i = 1; i <= 4; i++)
		{
			cin >> num >> num2;
			res = biggest_low_power(num, num2);
			cout << res << " ";
		}
		cout << endl;
		break;

	case 4:
		for (i = 1; i <= 4; i++)
		{
			cin >> num;
			res = part_sum(num);
			cout << res << " ";
		}
		cout << endl;
		break;

	case 5:
		//first case: val is assumed to placed in data1[4]
		dataSize = read_array(data1);
		partition(data1, dataSize);
		bubble_sort(data1, 4);
		bubble_sort(data1 + 5, dataSize - 5);
		printArr(data1, dataSize);

		//second case: val is assumed to placed in data1[0]
		dataSize = read_array(data1);
		partition(data1, dataSize);
		bubble_sort(data1 + 1, dataSize - 1);
		printArr(data1, dataSize);

		//third case: val is assumed to placed in data1[dataSize-1]
		dataSize = read_array(data1);
		partition(data1, dataSize);
		bubble_sort(data1, dataSize - 1);
		printArr(data1, dataSize);
		break;

	case 6:
		//read array
		dataSize1 = read_array(data1);
		dataSize2 = read_array(data2);
		// find average
		avg1 = find_avg(data1, dataSize1);
		avg2 = find_avg(data2, dataSize2);
		// sort array
		bubble_sort(data1, dataSize1);
		bubble_sort(data2, dataSize2);
		printArr(data1, dataSize1);
		printArr(data2, dataSize2);
		// find median
		median1 = find_median(data1, dataSize1);
		median2 = find_median(data2, dataSize2);
		cout << avg1 << " " << median1 << endl;
		cout << avg2 << " " << median2 << endl;
		break;

	case 7:
		//read the first array
		dataSize1 = read_array(data1);
		printArr(data1, dataSize1);
		//read the second array
		dataSize2 = read_array(data2);
		printArr(data2, dataSize2);
		//find average of 2 arrays
		avg_all = find_avg_two_arr(data1, data2, dataSize1, dataSize2);
		cout << avg_all << endl;
		break;

	case 8:
		for (i = 0; i < 3; i++)
		{
			//read and sort first array
			dataSize = read_array(data1);
			bubble_sort(data1, dataSize);
			printArr(data1, dataSize);
			//read and sort second array
			dataSize = read_array(data2);
			bubble_sort(data2, dataSize);
			printArr(data2, dataSize);
			//find median of 2 arrays
			median = find_median_two_arr(data1, data2, dataSize);
			cout << median << endl;
		}
		break;
	}
}


void printBoolRes(bool flag)
{ // This function prints true or false accoring to the value of flag

	if (flag)
		cout << "true ";
	else
		cout << "false ";
}

void printArr(int arr[], int size)
{ // This funct6ion prints the numbers contained in arr, where size is the logical size of arr

	int i; // index for loop

	for (i = 0; i < size; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;


}
